from typing import List


class Solution:
    def stoneGameIII(self, stones: List[int]) -> str:
        size = len(stones)

        # 定义状态矩阵：dp[i]=从i开始拿时：先手数量-后手数量
        dp = [float("-inf")] * size
        for i in range(size - 1, -1, -1):
            # 先手拿1个
            if i + 1 < size:
                dp[i] = max(dp[i], stones[i] - dp[i + 1])
            else:
                dp[i] = max(dp[i], stones[i])

            # 先手拿2个
            if i + 2 < size:
                dp[i] = max(dp[i], stones[i] + stones[i + 1] - dp[i + 2])
            elif i + 1 < size:
                dp[i] = max(dp[i], stones[i] + stones[i + 1])

            # 先手拿3个
            if i + 3 < size:
                dp[i] = max(dp[i], stones[i] + stones[i + 1] + stones[i + 2] - dp[i + 3])
            elif i + 2 < size:
                dp[i] = max(dp[i], stones[i] + stones[i + 1] + stones[i + 2])

        if dp[0] > 0:
            return "Alice"
        elif dp[0] < 0:
            return "Bob"
        else:
            return "Tie"


if __name__ == "__main__":
    print(Solution().stoneGameIII(stones=[1, 2, 3, 7]))  # "Bob"
    print(Solution().stoneGameIII(stones=[1, 2, 3, -9]))  # "Alice"
    print(Solution().stoneGameIII(stones=[1, 2, 3, 6]))  # "Tie"
    print(Solution().stoneGameIII(stones=[1, 2, 3, -1, -2, -3, 7]))  # "Alice"
    print(Solution().stoneGameIII(stones=[-1, -2, -3]))  # "Tie"
